package Arrays;

import java.util.Arrays;
import java.util.HashSet;

public class _41_FirstMissingPositive {
    //solution 1:use hashset
    public int firstMissingPositive(int[] nums) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        HashSet<Integer> sets = new HashSet<Integer>();
        for (int num : nums) {
            if (num > 0) {
                if(min>num) min = num;
                if(max<num) max = num;
                sets.add(num);
            }
        }
        if (min > 1) {
            return 1;
        } else {
            //check if there are missing positive between min and max
            for (int i = min; i <= max; i++) {
                if (!sets.contains(i)) {
                    return i;
                }
            }
            //if the numbers betweeen min and max is consequent,return max's next number
            return max + 1;
        }
    }

    //solution 2:use sort algorithm
    public int firstMissingPositive_2(int[] nums) {
        Arrays.sort(nums);
        int firstPositive = 1;
        for (int num : nums) {
            if (num == firstPositive) {
                firstPositive++;
            }
            //test cases has repeated numbers
            /* else {
                if (num > 0) {
                    return firstPositive;
                }
            }*/
        }
        return firstPositive;
    }
}
